package com.leetcode.algorithm.y19.m04;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;

import com.leetcode.algorithm.common.Employee;
import com.leetcode.algorithm.common.TreeNode;

/**
 * leetcode-cn.com
 * BFS专题
 * (done)690. 员工的重要性
 * (done)993. 二叉树的堂兄弟节点
 * (done)752. 打开转盘锁
 * @author: jie.deng
 * @time: 2019年4月2日 下午3:36:38
 */
public class MySolution0401 {
	
	/**
	 * 690. 员工的重要性
	 * 
	 * 给定一个保存员工信息的数据结构，它包含了员工唯一的id，重要度 和 直系下属的id。
	 * 
	 * 比如，员工1是员工2的领导，员工2是员工3的领导。他们相应的重要度为15, 10, 5。那么员工1的数据结构是[1, 15,
	 * [2]]，员工2的数据结构是[2, 10, [3]]，员工3的数据结构是[3, 5,
	 * []]。注意虽然员工3也是员工1的一个下属，但是由于并不是直系下属，因此没有体现在员工1的数据结构中。
	 * 
	 * 现在输入一个公司的所有员工信息，以及单个员工id，返回这个员工和他所有下属的重要度之和。
	 * 
	 * 示例 1:
	 * 
	 * 输入: [[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1 输出: 11 解释:
	 * 员工1自身的重要度是5，他有两个直系下属2和3，而且2和3的重要度均为3。因此员工1的总重要度是 5 + 3 + 3 = 11。 注意:
	 * 
	 * 一个员工最多有一个直系领导，但是可以有多个直系下属 员工数量不超过2000。
	 * 
	 * @param employees
	 * @param id
	 * @return
	 */
	public int getImportance(List<Employee> employees, int id) {
		if (employees == null || employees.size() == 0) {
			return 0;
		}

		Map<Integer, Integer> importanceMap = new HashMap<Integer, Integer>();
		Map<Integer, Employee> empMap = new HashMap<Integer, Employee>();
		// 遍历employees，准备importanceMap和empMap
		for (Employee emp : employees) {
			if (emp.subordinates == null || emp.subordinates.size() == 0) {
				// 当前员工没有直系下属
				if (emp.id == id) {
					return emp.importance;
				}
				importanceMap.put(emp.id, emp.importance);
			} else {
				empMap.put(emp.id, emp);
			}
		}

		Employee keyEmp = empMap.get(id);
		Queue<Employee> queue = new LinkedList<Employee>();
		queue.offer(keyEmp);
		Stack<Employee> stack = new Stack<Employee>();
		while (!queue.isEmpty()) {
			Employee cur = queue.poll();
			if (cur.subordinates != null && cur.subordinates.size() > 0) {
				stack.push(cur);
				for (Integer empId : cur.subordinates) {
					if (!importanceMap.containsKey(empId)) {
						queue.offer(empMap.get(empId));
					}
				}
			}
		}

		while (!stack.isEmpty()) {
			Employee cur = stack.pop();
			int importance = cur.importance;
			for (Integer empId : cur.subordinates) {
				importance += importanceMap.get(empId);
			}
			importanceMap.put(cur.id, importance);
		}

		return importanceMap.get(id);
	}
	
    /**
     * 993. 二叉树的堂兄弟节点
     * 
     * 在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。
     * 
     * 如果二叉树的两个节点深度相同，但父节点不同，则它们是一对堂兄弟节点。
     * 
     * 我们给出了具有唯一值的二叉树的根节点 root，以及树中两个不同节点的值 x 和 y。
     * 
     * 只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true。否则，返回 false。
     * 
     *  
     * 
     * 示例 1：
     * 
     * 
     * 输入：root = [1,2,3,4], x = 4, y = 3
     * 输出：false
     * 示例 2：
     * 
     * 
     * 输入：root = [1,2,3,null,4,null,5], x = 5, y = 4
     * 输出：true
     * 示例 3：
     * 
     * 
     * 
     * 输入：root = [1,2,3,null,4], x = 2, y = 3
     * 输出：false
     *  
     * 
     * 提示：
     * 
     * 二叉树的节点数介于 2 到 100 之间。
     * 每个节点的值都是唯一的、范围为 1 到 100 的整数。
     * @param root
     * @param x
     * @param y
     * @return
     */
	public boolean isCousins(TreeNode root, int x, int y) {
		if (root == null || (root.val == x || root.val == y)) {
			return false;
		}
		// 广度优先搜索，使用队列实现，先进先出
		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		queue.offer(root);
		while (!queue.isEmpty()) {
			List<Integer> levelList = new ArrayList<Integer>();
			int size = queue.size(); // 当前层次结点个数
			for (int i = 0; i < size; i++) {// 遍历当前层
				TreeNode node = queue.poll();
				levelList.add(node.val); // 遍历当前结点
				if (node.left != null) {
					queue.offer(node.left);
				}
				if (node.right != null) {
					queue.offer(node.right);
				}
				if (node.left != null && node.right != null 
						&& (((node.left.val ^ x) == 0 && (node.right.val ^ y) == 0) || ((node.left.val ^ y) == 0 && (node.right.val ^ x) == 0))) {
					// 兄弟结点的情况
					return false;
				}
			}
			if (levelList.contains(x)) {
				return levelList.contains(y);
			}
			if (levelList.contains(y)) {
				return levelList.contains(x);
			}
		}
		return false;
	}
	
    /**
     * 752. 打开转盘锁
     * 
	 * 你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转：例如把 '9' 变为  '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。
	 * 
	 * 锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。
	 * 
	 * 列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。
	 * 
	 * 字符串 target 代表可以解锁的数字，你需要给出最小的旋转次数，如果无论如何不能解锁，返回 -1。
	 * 
	 *  
	 * 
	 * 示例 1:
	 * 
	 * 输入：deadends = ["0201","0101","0102","1212","2002"], target = "0202"
	 * 输出：6
	 * 解释：
	 * 可能的移动序列为 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"。
	 * 注意 "0000" -> "0001" -> "0002" -> "0102" -> "0202" 这样的序列是不能解锁的，
	 * 因为当拨动到 "0102" 时这个锁就会被锁定。
	 * 示例 2:
	 * 
	 * 输入: deadends = ["8888"], target = "0009"
	 * 输出：1
	 * 解释：
	 * 把最后一位反向旋转一次即可 "0000" -> "0009"。
	 * 示例 3:
	 * 
	 * 输入: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
	 * 输出：-1
	 * 解释：
	 * 无法旋转到目标数字且不被锁定。
	 * 示例 4:
	 * 
	 * 输入: deadends = ["0000"], target = "8888"
	 * 输出：-1
	 *  
	 * 
	 * 提示：
	 * 
	 * 死亡列表 deadends 的长度范围为 [1, 500]。
	 * 目标数字 target 不会在 deadends 之中。
	 * 每个 deadends 和 target 中的字符串的数字会在 10,000 个可能的情况 '0000' 到 '9999' 中产生。
     * @param deadends
     * @param target
     * @return
     */
	public int openLock(String[] deadends, String target) {
		if (target.equals("0000")) {
			return 0;
		}

		Set<String> deadendSet = new HashSet<String>(deadends.length);
		for (int i = 0; i < deadends.length; i++) {
			if ("0000".equals(deadends[i])) {
				return -1;
			}
			deadendSet.add(deadends[i]);
		}

		// 判断 deadendSet 是否包含 target 的所有邻居，如果包含则返回-1
		int neighbourCnt = 0;
		for (int i = 0; i < 4; i++) {
			char ch = target.charAt(i);
			StringBuilder sbStr = new StringBuilder(target);
			sbStr.setCharAt(i, ch == '9' ? '0' : (char) (ch + 1));
			String str = sbStr.toString();
			if (deadendSet.contains(str)) {
				neighbourCnt++;
			}

			sbStr.setCharAt(i, ch == '0' ? '9' : (char) (ch - 1));
			str = sbStr.toString();
			if (deadendSet.contains(str)) {
				neighbourCnt++;
			}
		}
		if (neighbourCnt == 8) {
			return -1;
		}

		Set<String> visitedSet = new HashSet<String>(10000);
		Queue<String> queue = new LinkedList<String>();
		int level = 1;
		queue.offer("0000");
		visitedSet.add("0000");
		int levelSize = 1;
		while (!queue.isEmpty()) {
			for (int j = 0; j < levelSize; j++) {
				String curStr = queue.poll();

				// 将str的邻居加入queue
				for (int i = 0; i < 4; i++) {
					char ch = curStr.charAt(i);
					StringBuilder sbStr = new StringBuilder(curStr);
					sbStr.setCharAt(i, ch == '9' ? '0' : (char) (ch + 1));
					String str = sbStr.toString();
					if (!deadendSet.contains(str) && !visitedSet.contains(str)) {
						if (target.equals(str)) {
							return level;
						}
						visitedSet.add(str);
						queue.add(str);
					}

					sbStr.setCharAt(i, ch == '0' ? '9' : (char) (ch - 1));
					str = sbStr.toString();
					if (!deadendSet.contains(str) && !visitedSet.contains(str)) {
						if (target.equals(str)) {
							return level;
						}
						visitedSet.add(str);
						queue.add(str);
					}
				}
			}
			level++;
			levelSize = queue.size();
		}
		return -1;
	}

}
